// 方式1： 时间复杂度O(n^2)
function twoSum(nums: number[], target: number): number[] {
    const result:number[] = [];
    for (let i = 0; i < nums.length - 1; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                if (!result.includes(i)) result.push(i);
                if (!result.includes(j)) result.push(j);
            }
        }
    }
    return result;
}

// 方式2, 时间复杂度O(n)
function twoSum1(nums: number[], target: number): number[] {
    for (let i = 0; i < nums.length; i++) {
        const index = nums.indexOf(target - nums[i]);
        if (index !== -1 && index !== i) {
           return  [i, index];
        }
	}
    return [];
}

// 最优解 哈希表 时间复杂度O(n) 空间复杂度O(n)
function twoSum2(nums: number[], target: number): number[] {
	const map = new Map<number, number>();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (map.has(complement)) {
            return [map.get(complement)!, i];
        }
        map.set(nums[i], i);
    }
    return [];
}